home *** CD-ROM | disk | FTP | other *** search
/ Chip: 2001 Haziran / CHIP Haziran2001.iso / prog / share / 17 / dings_e.exe / Compiler / Include / stl_vector.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-08  |  17.0 KB  |  535 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26.  
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31. #ifndef __SGI_STL_INTERNAL_VECTOR_H
  32. #define __SGI_STL_INTERNAL_VECTOR_H
  33.  
  34. __STL_BEGIN_NAMESPACE 
  35.  
  36. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  37. #pragma set woff 1174
  38. #endif
  39.  
  40. template <class T, class Alloc = alloc>
  41. class vector {
  42. public:
  43.   typedef T value_type;
  44.   typedef value_type* pointer;
  45.   typedef const value_type* const_pointer;
  46.   typedef value_type* iterator;
  47.   typedef const value_type* const_iterator;
  48.   typedef value_type& reference;
  49.   typedef const value_type& const_reference;
  50.   typedef size_t size_type;
  51.   typedef ptrdiff_t difference_type;
  52.  
  53. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  54.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  55.   typedef reverse_iterator<iterator> reverse_iterator;
  56. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  57.   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  58.                            difference_type>  const_reverse_iterator;
  59.   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  60.           reverse_iterator;
  61. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  62. protected:
  63.   typedef simple_alloc<value_type, Alloc> data_allocator;
  64.   iterator start;
  65.   iterator finish;
  66.   iterator end_of_storage;
  67.   void insert_aux(iterator position, const T& x);
  68.   void deallocate() {
  69.     if (start) data_allocator::deallocate(start, end_of_storage - start);
  70.   }
  71.  
  72.   void fill_initialize(size_type n, const T& value) {
  73.     start = allocate_and_fill(n, value);
  74.     finish = start + n;
  75.     end_of_storage = finish;
  76.   }
  77. public:
  78.   iterator begin() { return start; }
  79.   const_iterator begin() const { return start; }
  80.   iterator end() { return finish; }
  81.   const_iterator end() const { return finish; }
  82.   reverse_iterator rbegin() { return reverse_iterator(end()); }
  83.   const_reverse_iterator rbegin() const { 
  84.     return const_reverse_iterator(end()); 
  85.   }
  86.   reverse_iterator rend() { return reverse_iterator(begin()); }
  87.   const_reverse_iterator rend() const { 
  88.     return const_reverse_iterator(begin()); 
  89.   }
  90.   size_type size() const { return size_type(end() - begin()); }
  91.   size_type max_size() const { return size_type(-1) / sizeof(T); }
  92.   size_type capacity() const { return size_type(end_of_storage - begin()); }
  93.   bool empty() const { return begin() == end(); }
  94.   reference operator[](size_type n) { return *(begin() + n); }
  95.   const_reference operator[](size_type n) const { return *(begin() + n); }
  96.  
  97.   vector() : start(0), finish(0), end_of_storage(0) {}
  98.   vector(size_type n, const T& value) { fill_initialize(n, value); }
  99.   vector(int n, const T& value) { fill_initialize(n, value); }
  100.   vector(long n, const T& value) { fill_initialize(n, value); }
  101.   explicit vector(size_type n) { fill_initialize(n, T()); }
  102.  
  103.   vector(const vector<T, Alloc>& x) {
  104.     start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
  105.     finish = start + (x.end() - x.begin());
  106.     end_of_storage = finish;
  107.   }
  108. #ifdef __STL_MEMBER_TEMPLATES
  109.   template <class InputIterator>
  110.   vector(InputIterator first, InputIterator last) :
  111.     start(0), finish(0), end_of_storage(0)
  112.   {
  113.     range_initialize(first, last, iterator_category(first));
  114.   }
  115. #else /* __STL_MEMBER_TEMPLATES */
  116.   vector(const_iterator first, const_iterator last) {
  117.     size_type n = 0;
  118.     distance(first, last, n);
  119.     start = allocate_and_copy(n, first, last);
  120.     finish = start + n;
  121.     end_of_storage = finish;
  122.   }
  123. #endif /* __STL_MEMBER_TEMPLATES */
  124.   ~vector() { 
  125.     destroy(start, finish);
  126.     deallocate();
  127.   }
  128.   vector<T, Alloc>& operator=(const vector<T, Alloc>& x);
  129.   void reserve(size_type n) {
  130.     if (capacity() < n) {
  131.       const size_type old_size = size();
  132.       iterator tmp = allocate_and_copy(n, start, finish);
  133.       destroy(start, finish);
  134.       deallocate();
  135.       start = tmp;
  136.       finish = tmp + old_size;
  137.       end_of_storage = start + n;
  138.     }
  139.   }
  140.   reference front() { return *begin(); }
  141.   const_reference front() const { return *begin(); }
  142.   reference back() { return *(end() - 1); }
  143.   const_reference back() const { return *(end() - 1); }
  144.   void push_back(const T& x) {
  145.     if (finish != end_of_storage) {
  146.       construct(finish, x);
  147.       ++finish;
  148.     }
  149.     else
  150.       insert_aux(end(), x);
  151.   }
  152.   void swap(vector<T, Alloc>& x) {
  153.     __STD::swap(start, x.start);
  154.     __STD::swap(finish, x.finish);
  155.     __STD::swap(end_of_storage, x.end_of_storage);
  156.   }
  157.   iterator insert(iterator position, const T& x) {
  158.     size_type n = position - begin();
  159.     if (finish != end_of_storage && position == end()) {
  160.       construct(finish, x);
  161.       ++finish;
  162.     }
  163.     else
  164.       insert_aux(position, x);
  165.     return begin() + n;
  166.   }
  167.   iterator insert(iterator position) { return insert(position, T()); }
  168. #ifdef __STL_MEMBER_TEMPLATES
  169.   template <class InputIterator>
  170.   void insert(iterator position, InputIterator first, InputIterator last) {
  171.     range_insert(position, first, last, iterator_category(first));
  172.   }
  173. #else /* __STL_MEMBER_TEMPLATES */
  174.   void insert(iterator position,
  175.               const_iterator first, const_iterator last);
  176. #endif /* __STL_MEMBER_TEMPLATES */
  177.  
  178.   void insert (iterator pos, size_type n, const T& x);
  179.   void insert (iterator pos, int n, const T& x) {
  180.     insert(pos, (size_type) n, x);
  181.   }
  182.   void insert (iterator pos, long n, const T& x) {
  183.     insert(pos, (size_type) n, x);
  184.   }
  185.  
  186.   void pop_back() {
  187.     --finish;
  188.     destroy(finish);
  189.   }
  190.   iterator erase(iterator position) {
  191.     if (position + 1 != end())
  192.       copy(position + 1, finish, position);
  193.     --finish;
  194.     destroy(finish);
  195.     return position;
  196.   }
  197.   iterator erase(iterator first, iterator last) {
  198.     iterator i = copy(last, finish, first);
  199.     destroy(i, finish);
  200.     finish = finish - (last - first);
  201.     return first;
  202.   }
  203.   void resize(size_type new_size, const T& x) {
  204.     if (new_size < size()) 
  205.       erase(begin() + new_size, end());
  206.     else
  207.       insert(end(), new_size - size(), x);
  208.   }
  209.   void resize(size_type new_size) { resize(new_size, T()); }
  210.   void clear() { erase(begin(), end()); }
  211.  
  212. protected:
  213.   iterator allocate_and_fill(size_type n, const T& x) {
  214.     iterator result = data_allocator::allocate(n);
  215.     __STL_TRY {
  216.       uninitialized_fill_n(result, n, x);
  217.       return result;
  218.     }
  219.     __STL_UNWIND(data_allocator::deallocate(result, n));
  220.   }
  221.  
  222. #ifdef __STL_MEMBER_TEMPLATES
  223.   template <class ForwardIterator>
  224.   iterator allocate_and_copy(size_type n,
  225.                              ForwardIterator first, ForwardIterator last) {
  226.     iterator result = data_allocator::allocate(n);
  227.     __STL_TRY {
  228.       uninitialized_copy(first, last, result);
  229.       return result;
  230.     }
  231.     __STL_UNWIND(data_allocator::deallocate(result, n));
  232.   }
  233. #else /* __STL_MEMBER_TEMPLATES */
  234.   iterator allocate_and_copy(size_type n,
  235.                              const_iterator first, const_iterator last) {
  236.     iterator result = data_allocator::allocate(n);
  237.     __STL_TRY {
  238.       uninitialized_copy(first, last, result);
  239.       return result;
  240.     }
  241.     __STL_UNWIND(data_allocator::deallocate(result, n));
  242.   }
  243. #endif /* __STL_MEMBER_TEMPLATES */
  244.  
  245.  
  246. #ifdef __STL_MEMBER_TEMPLATES
  247.   template <class InputIterator>
  248.   void range_initialize(InputIterator first, InputIterator last,
  249.                         input_iterator_tag) {
  250.     for ( ; first != last; ++first)
  251.       push_back(*first);
  252.   }
  253.  
  254.   // This function is only called by the constructor.  We have to worry
  255.   //  about resource leaks, but not about maintaining invariants.
  256.   template <class ForwardIterator>
  257.   void range_initialize(ForwardIterator first, ForwardIterator last,
  258.                         forward_iterator_tag) {
  259.     size_type n = 0;
  260.     distance(first, last, n);
  261.     start = allocate_and_copy(n, first, last);
  262.     finish = start + n;
  263.     end_of_storage = finish;
  264.   }
  265.  
  266.   template <class InputIterator>
  267.   void range_insert(iterator pos,
  268.                     InputIterator first, InputIterator last,
  269.                     input_iterator_tag);
  270.  
  271.   template <class ForwardIterator>
  272.   void range_insert(iterator pos,
  273.                     ForwardIterator first, ForwardIterator last,
  274.                     forward_iterator_tag);
  275.  
  276. #endif /* __STL_MEMBER_TEMPLATES */
  277. };
  278.  
  279. template <class T, class Alloc>
  280. inline bool operator==(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {
  281.   return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  282. }
  283.  
  284. template <class T, class Alloc>
  285. inline bool operator<(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {
  286.   return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  287. }
  288.  
  289. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  290.  
  291. template <class T, class Alloc>
  292. inline void swap(vector<T, Alloc>& x, vector<T, Alloc>& y) {
  293.   x.swap(y);
  294. }
  295.  
  296. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  297.  
  298. template <class T, class Alloc>
  299. vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {
  300.   if (&x != this) {
  301.     if (x.size() > capacity()) {
  302.       iterator tmp = allocate_and_copy(x.end() - x.begin(),
  303.                                        x.begin(), x.end());
  304.       destroy(start, finish);
  305.       deallocate();
  306.       start = tmp;
  307.       end_of_storage = start + (x.end() - x.begin());
  308.     }
  309.     else if (size() >= x.size()) {
  310.       iterator i = copy(x.begin(), x.end(), begin());
  311.       destroy(i, finish);
  312.     }
  313.     else {
  314.       copy(x.begin(), x.begin() + size(), start);
  315.       uninitialized_copy(x.begin() + size(), x.end(), finish);
  316.     }
  317.     finish = start + x.size();
  318.   }
  319.   return *this;
  320. }
  321.  
  322. template <class T, class Alloc>
  323. void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  324.   if (finish != end_of_storage) {
  325.     construct(finish, *(finish - 1));
  326.     ++finish;
  327.     T x_copy = x;
  328.     copy_backward(position, finish - 2, finish - 1);
  329.     *position = x_copy;
  330.   }
  331.   else {
  332.     const size_type old_size = size();
  333.     const size_type len = old_size != 0 ? 2 * old_size : 1;
  334.     iterator new_start = data_allocator::allocate(len);
  335.     iterator new_finish = new_start;
  336.     __STL_TRY {
  337.       new_finish = uninitialized_copy(start, position, new_start);
  338.       construct(new_finish, x);
  339.       ++new_finish;
  340.       new_finish = uninitialized_copy(position, finish, new_finish);
  341.     }
  342.  
  343. #       ifdef  __STL_USE_EXCEPTIONS 
  344.     catch(...) {
  345.       destroy(new_start, new_finish); 
  346.       data_allocator::deallocate(new_start, len);
  347.       throw;
  348.     }
  349. #       endif /* __STL_USE_EXCEPTIONS */
  350.     destroy(begin(), end());
  351.     deallocate();
  352.     start = new_start;
  353.     finish = new_finish;
  354.     end_of_storage = new_start + len;
  355.   }
  356. }
  357.  
  358. template <class T, class Alloc>
  359. void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  360.   if (n != 0) {
  361.     if (size_type(end_of_storage - finish) >= n) {
  362.       T x_copy = x;
  363.       const size_type elems_after = finish - position;
  364.       iterator old_finish = finish;
  365.       if (elems_after > n) {
  366.         uninitialized_copy(finish - n, finish, finish);
  367.         finish += n;
  368.         copy_backward(position, old_finish - n, old_finish);
  369.         fill(position, position + n, x_copy);
  370.       }
  371.       else {
  372.         uninitialized_fill_n(finish, n - elems_after, x_copy);
  373.         finish += n - elems_after;
  374.         uninitialized_copy(position, old_finish, finish);
  375.         finish += elems_after;
  376.         fill(position, old_finish, x_copy);
  377.       }
  378.     }
  379.     else {
  380.       const size_type old_size = size();        
  381.       const size_type len = old_size + max(old_size, n);
  382.       iterator new_start = data_allocator::allocate(len);
  383.       iterator new_finish = new_start;
  384.       __STL_TRY {
  385.         new_finish = uninitialized_copy(start, position, new_start);
  386.         new_finish = uninitialized_fill_n(new_finish, n, x);
  387.         new_finish = uninitialized_copy(position, finish, new_finish);
  388.       }
  389. #         ifdef  __STL_USE_EXCEPTIONS 
  390.       catch(...) {
  391.         destroy(new_start, new_finish);
  392.         data_allocator::deallocate(new_start, len);
  393.         throw;
  394.       }
  395. #         endif /* __STL_USE_EXCEPTIONS */
  396.       destroy(start, finish);
  397.       deallocate();
  398.       start = new_start;
  399.       finish = new_finish;
  400.       end_of_storage = new_start + len;
  401.     }
  402.   }
  403. }
  404.  
  405. #ifdef __STL_MEMBER_TEMPLATES
  406.  
  407. template <class T, class Alloc> template <class InputIterator>
  408. void vector<T, Alloc>::range_insert(iterator pos,
  409.                                     InputIterator first, InputIterator last,
  410.                                     input_iterator_tag) {
  411.   for ( ; first != last; ++first) {
  412.     pos = insert(pos, *first);
  413.     ++pos;
  414.   }
  415. }
  416.  
  417. template <class T, class Alloc> template <class ForwardIterator>
  418. void vector<T, Alloc>::range_insert(iterator position,
  419.                                     ForwardIterator first,
  420.                                     ForwardIterator last,
  421.                                     forward_iterator_tag) {
  422.   if (first != last) {
  423.     size_type n = 0;
  424.     distance(first, last, n);
  425.     if (size_type(end_of_storage - finish) >= n) {
  426.       const size_type elems_after = finish - position;
  427.       iterator old_finish = finish;
  428.       if (elems_after > n) {
  429.         uninitialized_copy(finish - n, finish, finish);
  430.         finish += n;
  431.         copy_backward(position, old_finish - n, old_finish);
  432.         copy(first, last, position);
  433.       }
  434.       else {
  435.         ForwardIterator mid = first;
  436.         advance(mid, elems_after);
  437.         uninitialized_copy(mid, last, finish);
  438.         finish += n - elems_after;
  439.         uninitialized_copy(position, old_finish, finish);
  440.         finish += elems_after;
  441.         copy(first, mid, position);
  442.       }
  443.     }
  444.     else {
  445.       const size_type old_size = size();
  446.       const size_type len = old_size + max(old_size, n);
  447.       iterator new_start = data_allocator::allocate(len);
  448.       iterator new_finish = new_start;
  449.       __STL_TRY {
  450.         new_finish = uninitialized_copy(start, position, new_start);
  451.         new_finish = uninitialized_copy(first, last, new_finish);
  452.         new_finish = uninitialized_copy(position, finish, new_finish);
  453.       }
  454. #         ifdef __STL_USE_EXCEPTIONS
  455.       catch(...) {
  456.         destroy(new_start, new_finish);
  457.         data_allocator::deallocate(new_start, len);
  458.         throw;
  459.       }
  460. #         endif /* __STL_USE_EXCEPTIONS */
  461.       destroy(start, finish);
  462.       deallocate();
  463.       start = new_start;
  464.       finish = new_finish;
  465.       end_of_storage = new_start + len;
  466.     }
  467.   }
  468. }
  469.  
  470. #else /* __STL_MEMBER_TEMPLATES */
  471.  
  472. template <class T, class Alloc>
  473. void vector<T, Alloc>::insert(iterator position, 
  474.                               const_iterator first, 
  475.                               const_iterator last) {
  476.   if (first != last) {
  477.     size_type n = 0;
  478.     distance(first, last, n);
  479.     if (size_type(end_of_storage - finish) >= n) {
  480.       const size_type elems_after = finish - position;
  481.       iterator old_finish = finish;
  482.       if (elems_after > n) {
  483.         uninitialized_copy(finish - n, finish, finish);
  484.         finish += n;
  485.         copy_backward(position, old_finish - n, old_finish);
  486.         copy(first, last, position);
  487.       }
  488.       else {
  489.         uninitialized_copy(first + elems_after, last, finish);
  490.         finish += n - elems_after;
  491.         uninitialized_copy(position, old_finish, finish);
  492.         finish += elems_after;
  493.         copy(first, first + elems_after, position);
  494.       }
  495.     }
  496.     else {
  497.       const size_type old_size = size();
  498.       const size_type len = old_size + max(old_size, n);
  499.       iterator new_start = data_allocator::allocate(len);
  500.       iterator new_finish = new_start;
  501.       __STL_TRY {
  502.         new_finish = uninitialized_copy(start, position, new_start);
  503.         new_finish = uninitialized_copy(first, last, new_finish);
  504.         new_finish = uninitialized_copy(position, finish, new_finish);
  505.       }
  506. #         ifdef __STL_USE_EXCEPTIONS
  507.       catch(...) {
  508.         destroy(new_start, new_finish);
  509.         data_allocator::deallocate(new_start, len);
  510.         throw;
  511.       }
  512. #         endif /* __STL_USE_EXCEPTIONS */
  513.       destroy(start, finish);
  514.       deallocate();
  515.       start = new_start;
  516.       finish = new_finish;
  517.       end_of_storage = new_start + len;
  518.     }
  519.   }
  520. }
  521.  
  522. #endif /* __STL_MEMBER_TEMPLATES */
  523.  
  524. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  525. #pragma reset woff 1174
  526. #endif
  527.  
  528. __STL_END_NAMESPACE 
  529.  
  530. #endif /* __SGI_STL_INTERNAL_VECTOR_H */
  531.  
  532. // Local Variables:
  533. // mode:C++
  534. // End:
  535.